// 216.[DFS递归不重复] 组合总和 III (k个数和为n)
// https://leetcode.cn/problems/combination-sum-iii
// 找出所有相加之和为n的k个数的组合，且满足下列条件
//【只使用数字1到9，每个数字最多使用一次】
// 返回所有可能的有效组合的列表。
// 该列表不能包含相同的组合两次，组合可以以任何顺序返回。
// 输入: k = 3, n = 7
// 输出: [[1,2,4]]
// 1 + 2 + 4 = 7
// 没有其他符合的组合了。
// 输入: k = 3, n = 9
// 输出: [[1,2,6], [1,3,5], [2,3,4]]
// 1 + 2 + 6 = 9
// 1 + 3 + 5 = 9
// 2 + 3 + 4 = 9
// 没有其他符合的组合了。
// 输入: k = 4, n = 1
// 输出: []
// 解释: 不存在有效的组合。
// 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 >
// 1，没有有效的组合。 2 <= k <= 9，1 <= n <= 60

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution {
 public:
  vector<vector<int>> result;
  vector<int> path;
  void dfs(int kCnt, int sumTarget, int sum, int level) {
    if (path.size() == kCnt) {
      if (sum == sumTarget) result.push_back(path);
      return;
    }
    //每层i从L开始枚举,下层从i+1 开始枚举,枚举组合数的模板写法
    for (int iVal = level; iVal <= 9; ++iVal) {
      path.push_back(iVal);
      dfs(kCnt, sumTarget, sum + iVal, iVal + 1);
      path.pop_back();
    }
  }
  // sumTarget 的 kCnt 个数的组合
  vector<vector<int>> combinationSum3(int kCnt, int sumTarget) {
    dfs(kCnt, sumTarget, 0, 1);
    return result;
  }
};
